package leetcode;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Day25 {
    public boolean wordBreak(String s, List<String> wordDict) {
            Set<String> hash=new HashSet(wordDict);
            int n=s.length();
            boolean[] dp=new boolean[n+1];
            dp[0]=true;
            s=" "+s;
            for(int i=1;i<=n;i++){
                for(int j=i;j>=1;j--){
                    if(dp[j-1]&&hash.contains(s.substring(j,i+1))){
                        dp[i]=true;
                        break;
                    }
                }
            }
            return dp[n];
    }
    public boolean canJump(int[] nums) {
        int k=0;
        int n=nums.length;
        for(int i=0;i<n;i++){
            if(i>k){
                return false;
            }
            k=Math.max(k,nums[i]+i);
        }
        return true;
    }
}
